package _18_剑指OfferII;

import java.util.*;

public class _115_剑指OfferII重建序列 {

    // 拓扑排序
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        // 不符合条件
        if (seqs == null || seqs.size() == 0 || seqs.get(0).size() == 0) return false;
        // 找出最大值
        int max = 0;
        for (int i : org) {
            max = Math.max(i, max);
        }
        List<Integer>[] lists = new ArrayList[max];
        int[] values = new int[max];

        if (!buildTopoLogic(seqs, lists, values, max)) return false;

        int[] compare = new int[org.length];
        int index = 0;
        Arrays.fill(compare, -1);

        Queue<Integer> queue = new LinkedList<>();
        // 找出入度为0
        for (int i = 0; i < values.length; ++i) {
            if (values[i] == 0) {
                queue.add(i + 1);
            }
        }

        while (!queue.isEmpty()) {
            if (queue.size() > 1) return false;
            int ele = queue.poll();
            compare[index++] = ele;
            values[ele - 1]--;
            ArrayList<Integer> tos = (ArrayList<Integer>) lists[ele - 1];
            if (tos == null) break;
            for (Integer to : tos) {
                if (--values[to - 1] == 0) {
                    queue.add(to);
                }
            }
        }

        for (int value : values) {
            if (value != -1) return false;
        }

        // 对比数据
        for (int i = 0; i < index; ++i) {
            if (org[i] == compare[i]) continue;
            return false;
        }
        return index != 0;
    }

    private boolean buildTopoLogic(List<List<Integer>> seqs, List<Integer>[] lists, int[] values, int max) {

        // check logic
        for (List<Integer> seq : seqs) {
            for (Integer integer : seq) {
                if (integer > max || integer < 1) return false;
                if (values[integer - 1] != -1) values[integer - 1] = 0;
            }
        }

        for (List<Integer> seq : seqs) {
            int size = seq.size();
            for (int i = 1; i < size; ++i) {
                int from = seq.get(i - 1);
                int to = seq.get(i);
                if (lists[from - 1] == null) lists[from - 1] = new ArrayList<>();
                lists[from - 1].add(to);
                values[to - 1]++;
            }
        }
        return true;
    }

}
